#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    static const int N = 15;
    int res = 0;
    vector<int> g[N];

    int dp[N][N];
    int numWays(int n, vector<vector<int>> &relation, int k)
    {
        for (auto r : relation)
        {
            g[r[0]].push_back(r[1]); // r[0]->r[1]
        }

        dp[0][0] = 1;

        for (int i = 0; i < k; i++)
            for (int j = 0; j < n; j++)
                // 枚举j的出边
                for (auto k : g[j]) // j->k
                {
                    if (dp[i][j] >= 0)
                        dp[i + 1][k] += dp[i][j];
                }

        return dp[k][n-1];
    }
};

int main()
{
    int n, k, q;
    vector<vector<int>> rs;

    cin >> n >> k;
    while (q--)
    {
        vector<int> r(2);
        cin >> r[0] >> r[1];
        rs.push_back(r);
    }
    Solution s;
    cout << s.numWays(n, rs, k) << endl;
    return 0;
}

/*
5 3 7
0 2
2 1
3 4
2 3
1 4
2 0
0 4
*/
